package cn.edu.jxau.test;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;

/**
 * https://segmentfault.com/a/1190000004232716
 * @author 付大石
 *
 */
public class Sort {

    public static void main(String[] args) throws IOException {

        int len = 10000;
        int[] arr = new int[len];
        DataInputStream in = new DataInputStream(new FileInputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.readInt();
        }
        in.close();

        System.out.println(Arrays.toString(arr));
        long start = System.nanoTime();
        sort(arr);
        long end = System.nanoTime();
        System.out.println("spend tiem:" + (end - start));
        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 自底向上归并
     * @param arr
     */
//    private static void sort(int[] arr) {
//
//        int[] aux = new int[arr.length]; // 辅助空间
//        for (int size = 1; size < arr.length; size *= 2) {
//            for (int low = 0; low < arr.length - size; low = low + size + size) {
//                merge(arr, aux, low, low + size - 1, Math.min(low + size + size - 1, arr.length-1));
//            }
//        }
//    }

    /**
     * 归并排序：将两个有序数组归并为一个更大的有序数组
     * 
     * 1.空间复杂度为O(n)
     * @param arr
     */
    private static void sort(int[] arr) {

        int[] aux = new int[arr.length];
        sort(arr, aux, 0, arr.length - 1);
    }

    /**
     * 
     * @param arr
     * @param aux 辅助空间
     * @param lo
     * @param hi
     */
    private static void sort(int[] arr, int[] aux, int low, int high) {

        // 优化：小规模子数组使用插入排序
//        if (high - low < 10) {
//            for (int i = low + 1; i <= high; i++) {
//                int j = i;
//                int temp = arr[j];
//                while (j > low && temp < arr[j - 1]) {
//                    arr[j] = arr[j - 1];
//                    j--;
//                }
//                arr[j] = temp;
//            }
//            return;
//        }

        if (high <= low) {
            return;
        }
        int mid = (low + high) / 2;
        sort(arr, aux, low, mid);
        sort(arr, aux, mid + 1, high);

        // 优化：测试数组是否已经有序
//        if (arr[mid] <= arr[mid + 1]) { // 数组已经有序，无序归并处理
//            return;
//        }

        merge(arr, aux, low, mid, high);
    }

    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {

        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) { // 将arr复制到辅助数组中
            aux[k] = arr[k];
        }

        // 归并 //
        for (int k = low; k <= high; k++) {

            if (i > mid) { // 左半边已耗尽
                arr[k] = aux[j++];
            } else if (j > high) { // 右半边已耗尽
                arr[k] = aux[i++];
            } else if (aux[i] < aux[j]) {
                arr[k] = aux[i++];
            } else {
                arr[k] = aux[j++];
            }
        }

        // 优化：从两端归并，减少逻辑判断
//        for (int k = low; k <= mid; k++) {
//            aux[k] = arr[k];
//        }
//        for (int k = mid + 1; k <= high; k++) {
//            aux[k] = arr[high - k + mid + 1];
//        }
//        int i = low;
//        int j = high;
//        for (int k = low; k <= high; k++) {
//            if (aux[i] < aux[j]) {
//                arr[k] = aux[i++];
//            } else {
//                arr[k] = aux[j--];
//            }
//        }
    }
}
